/*
题目: 至少有 1 位重复的数字
给定正整数 n，返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。

https://leetcode.cn/problems/numbers-with-repeated-digits/
 */
public class NumDupDigitsAtMostN {
    // 直接求目标集合, 也可以利用逆向思维, 速度更快
    char[] cs = null;
    int size = 0;
    int[][][] memo = null;

    public int numDupDigitsAtMostN(int n) {
        cs = String.valueOf(n).toCharArray();
        size = cs.length;

        // 由于要记录至少一位重复数字, 所以我们要记录所有整数的出现情况
        // 最后一个容量表示 是否有重复, 重复即为 1, 没重复为 0
        memo = new int[size][1 << 10][2];
        for (int i = 0; i < size; i ++)
            for (int j = 0; j < (1 << 10); j ++)
                Arrays.fill(memo[i][j], -1);


        return dfs(0, 0, true, false, 0);
    }

    private int dfs(int pos, int mark, boolean limited, boolean hasNum, int isRepeat) {
        if (pos >= size) {
            return isRepeat;
        }

        if (!limited && memo[pos][mark][isRepeat] != -1) {
            return memo[pos][mark][isRepeat];
        }

        int src = 0;
        // 如果前面没有数字, 这里也可以不选择数字
        if (!hasNum) {
            src += dfs(pos + 1, mark, false, false, 0);
        }

        for (int i = hasNum ? 0 : 1, up = limited ? cs[pos] - '0' : 9; i <= up; i ++) {
            if (((mark >> i) & 1) == 1)  // 重复了
                src += dfs(pos + 1, mark, limited && i == up, true, 1);
            else
                src += dfs(pos + 1, mark | (1 << i), limited && i == up, true, isRepeat);
        }

        if (!limited) {
            memo[pos][mark][isRepeat] = src;
        }
        return src;
    }
}
